최단 경로 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

최단 경로 문제는 그래프에서 두 노드 사이의 가장 짧은 경로를 찾는 문제로, 다양한 종류와 알고리즘이 존재한다. 그래프의 종류에 따라 무방향, 방향, 혼합 그래프에서 정의될 수 있으며, 단일 쌍, 단일 출발점, 단일 도착점, 모든 쌍 최단 경로 문제로 세분화된다. 주요 알고리즘으로는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와셜 알고리즘 등이 있으며, 문제의 특성에 따라 적합한 알고리즘을 선택하여 해결한다. 이 문제는 웹 지도, 교통, 로봇 공학, 게임, 네트워크 등 다양한 분야에 응용되며, 실생활의 문제 해결에 기여한다.

더 읽어볼만한 페이지

다항 시간 문제 - 플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 동적 계획법의 일종으로, 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾아 시간 복잡도 O(N^3)으로 계산하며, 유향 그래프의 최단 경로 탐색 등 다양한 문제에 적용된다.
다항 시간 문제 - 벨먼-포드 알고리즘
벨만-포드 알고리즘은 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이며, 음수 가중치 간선이 있는 그래프에도 적용 가능하지만 음수 사이클이 존재하면 최단 경로를 찾을 수 없고 음수 사이클 탐지에 활용되며, 시간 복잡도는 O(|V| * |E|)이다.
그래프 이론의 계산 문제 - 외판원 문제
외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다.
그래프 이론의 계산 문제 - 해밀턴 경로
해밀턴 경로는 그래프의 모든 꼭짓점을 한 번씩 방문하는 경로로, 해밀턴 순환은 이러한 경로가 순환 형태를 띠는 것을 의미하며, 이들은 그래프 이론에서 중요한 개념으로 NP-완전 문제 및 외판원 문제 등에 응용된다.
네트워크 이론 - 사회 연결망
사회 연결망 분석은 개인이나 집단 간의 관계를 분석하여 사회적 구조와 행동을 이해하는 학제 간 연구 방법론으로, 다양한 이론적 틀을 활용하여 네트워크 내 위치와 정보 접근의 중요성을 분석하며 여러 분야에서 활용된다.
네트워크 이론 - 중심성
중심성은 그래프 이론에서 네트워크 내 노드의 중요성을 평가하기 위한 지표로, 차수 중심성, 근접 중심성 등 다양한 종류가 있으며 네트워크 흐름, 워크 구조 등 다양한 특징에 따라 분류된다.

최단 경로 문제
개요
분야	그래프 이론, 알고리즘
문제 유형	최적화 문제
설명
입력	가중치가 있는 그래프 (G = (V, E))
출력	주어진 두 정점 사이의 최단 경로
변종
단일 출발지 최단 경로	주어진 정점에서 그래프 내 다른 모든 정점까지의 최단 경로를 찾음.
단일 목적지 최단 경로	그래프 내 모든 정점에서 주어진 목적지 정점까지의 최단 경로를 찾음.
모든 쌍 최단 경로	그래프 내 모든 정점 쌍 사이의 최단 경로를 찾음.
알고리즘
가중치가 없는 그래프	너비 우선 탐색
비음수 가중치 그래프	다이크스트라 알고리즘
임의 가중치 그래프	벨만-포드 알고리즘, SPFA 알고리즘
모든 쌍 최단 경로	플로이드-워셜 알고리즘, 존슨 알고리즘
복잡도
다이크스트라 알고리즘 (피보나치 힙 사용)	O(\|E\| + \|V\| log \|V\|)
벨만-포드 알고리즘	O(\|V\|\|E\|)
플로이드-워셜 알고리즘	O(\|V\|^3)
응용

2. 최단 경로 문제의 정의 및 종류

최단 경로 문제는 그래프 이론의 핵심 문제 중 하나로, 그래프의 종류(무방향, 방향, 혼합)에 관계없이 적용할 수 있다.^[2]

최단 경로 문제는 문제 해결 방식에 따라 다음과 같이 분류할 수 있다.

'''단일 쌍 최단 경로 문제''': 주어진 두 꼭짓점 사이의 최단 경로를 찾는다.
'''단일 출발점 최단 경로 문제''': 한 출발점에서 다른 모든 꼭짓점까지의 최단 경로를 찾는다.
'''단일 도착점 최단 경로 문제''': 방향 그래프에서 모든 꼭짓점에서 한 도착점까지의 최단 경로를 찾는다.
'''모든 쌍 최단 경로 문제''': 그래프 내 모든 꼭짓점 쌍 사이의 최단 경로를 찾는다.

이러한 문제들은 단일 쌍 최단 경로 알고리즘을 반복 적용하는 것보다 더 효율적인 알고리즘을 가질 수 있다.

2. 1. 정의

그래프는 노드(정점)와 간선(변)으로 구성되며, 각 간선에는 가중치(거리, 시간, 비용 등)가 할당될 수 있다. 최단 경로 문제는 주어진 두 노드 사이의 경로 중 간선 가중치의 합이 최소가 되는 경로를 찾는 문제이다.^[2]

최단 경로 문제는 그래프에 대해 정의될 수 있으며, 무방향, 방향, 혼합 그래프 모두에 해당한다. 무방향 그래프에서 모든 간선은 어느 방향으로든 통과할 수 있다. 방향 그래프는 연속된 꼭짓점이 적절한 방향 간선으로 연결되어야 한다.^[2]

두 꼭짓점은 공통 간선에 인접할 때 서로 인접한다. 무방향 그래프에서 경로는 꼭짓점의 수열

P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \cdots \times V

이며, 여기서

v_i

는

1 \leq i < n

에 대해

v_{i+1}

에 인접한다. 이러한 경로

P

는

v_1

에서

v_n

까지의 길이

n-1

의 경로라고 한다.

E = \{e_{i, j}\}

이고

e_{i, j}

는

v_i

와

v_j

에 모두 인접한 간선이라고 하자. 실수 값 가중치 함수

f: E \rightarrow \mathbb{R}

와 무방향 (단순) 그래프

G

가 주어지면,

v

에서

v'

까지의 최단 경로는 모든 가능한

n

에 대해 합

\sum_{i =1}^{n-1} f(e_{i, i+1})

을 최소화하는 경로

P = ( v_1, v_2, \ldots, v_n )

이다(여기서

v_1 = v

이고

v_n = v'

). 그래프의 각 간선이 단위 가중치, 즉

f: E \rightarrow \{1\}

를 가질 때, 이것은 가장 적은 수의 간선을 가진 경로를 찾는 것과 같다.

이 문제는 때때로 다음과 같은 변형과 구별하기 위해 '''단일 쌍 최단 경로 문제'''라고도 한다.

'''단일 출발점 최단 경로 문제''': 그래프에서 출발 꼭짓점 ''v''에서 다른 모든 꼭짓점까지의 최단 경로를 찾는다.
'''단일 도착점 최단 경로 문제''': 방향 그래프의 모든 꼭짓점에서 단일 도착점 꼭짓점 ''v''까지의 최단 경로를 찾는다. 이것은 방향 그래프의 아크를 뒤집어서 단일 출발점 최단 경로 문제로 줄일 수 있다.
'''모든 쌍 최단 경로 문제''': 그래프의 모든 꼭짓점 쌍 ''v'', ''v' '' 사이의 최단 경로를 찾는다.

2. 2. 종류

최단 경로 문제는 주어진 그래프에서 특정 조건을 만족하는 가장 짧은 경로를 찾는 문제이다. 이 문제는 다음과 같이 세분화될 수 있다.

'''두 정점 간 최단 경로 문제''': 주어진 두 노드 사이의 최단 경로를 찾는다. 일반적으로 단일 시작점 최단 경로 문제의 알고리즘을 사용한다.^[2]
'''단일 출발점 최단 경로 문제 (SSSP: Single Source Shortest Path)''': 하나의 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는다. 이 문제를 해결하는 알고리즘으로는 다익스트라 알고리즘이나 벨만-포드 알고리즘이 잘 알려져 있다.^[2]
'''단일 도착점 최단 경로 문제''': 모든 노드에서 하나의 도착 노드까지의 최단 경로를 찾는다. 방향 그래프의 경우, 간선의 방향을 뒤집으면 단일 출발점 문제로 변환 가능하다.^[2]
'''모든 쌍 최단 경로 문제 (APSP: All Pair Shortest Path)''': 그래프 내의 모든 노드 쌍 사이의 최단 경로를 찾는다. 이 문제를 해결하는 알고리즘으로는 플로이드-워셜 알고리즘이 알려져 있다.^[2]

모든 쌍 최단 경로 문제와 같이, 알고리즘 과정에서 얻은 정보를 활용하여 계산량을 줄이는 것이 가능한 경우가 있다. 즉, 모든 쌍 최단 경로 문제는 단순히 두 정점 간 최단 경로 문제나 단일 출발점 최단 경로 문제를 반복적으로 해결하는 것보다 효율적일 수 있다.

3. 주요 알고리즘

최단 경로 문제는 그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 문제로, 다양한 알고리즘을 통해 해결할 수 있다. 그래프의 특성(가중치 유무, 음수 가중치 존재 여부 등)에 따라 적합한 알고리즘을 선택해야 한다.

데이크스트라 알고리즘: 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제를 해결할 수 있다. 특히 음이 아닌 가중치를 갖는 그래프에서 효율적이다.^[5]
벨먼-포드 알고리즘: 변의 가중치가 음수인 경우에도 단일 출발점 최단 경로 문제를 해결할 수 있다.^[5]
A* 탐색 알고리즘: 휴리스틱 방법을 사용하여 탐색 속도를 높여 단일 쌍 최단 경로 문제를 해결한다.
플로이드-와셜 알고리즘: 모든 쌍 최단 경로 문제를 해결한다.
존슨 알고리즘: 모든 쌍 최단 경로 문제를 해결하며, 희소 그래프에서 플로이드-와셜 알고리즘보다 빠를 수 있다.^[1]
비터비 알고리즘: 각 노드에 추가적인 확률 가중치를 사용하여 최단 확률 경로 문제를 해결한다.

다음 표는 주요 알고리즘과 시간 복잡도를 나타낸다.

알고리즘	시간 복잡도	저자
벨만-포드 알고리즘	$O(VE)$
다익스트라 알고리즘 (리스트)	$O(V^2)$
다익스트라 알고리즘 (수정된 이진 힙)	$O((E+V) \log{V})$
다익스트라 알고리즘 (피보나치 힙)	$O(E+V \log{V})$
	$O(E+V \sqrt{\log{L}})$

3. 1. 단일 출발점 최단 경로 알고리즘

데이크스트라 알고리즘은 음이 아닌 가중치를 갖는 그래프에서 단일 출발점 최단 경로를 찾는 알고리즘이다.^[5] 벨만-포드 알고리즘은 간선 가중치가 음수일 수 있는 경우에도 단일 출발점 최단 경로 문제를 해결한다. A* 탐색 알고리즘은 휴리스틱을 사용하여 탐색 속도를 높여 단일 쌍 최단 경로를 찾는다.

최단 경로의 거리는 부분 구조 최적성이 성립하며, 다음 점화식이 성립한다.

:

V

가 정점,

E

가 변,

c(s, v)

가 변의 가중치,

\mathrm{dist}(s, v)

가 최단 경로의 거리.

s, v, w \in V

。

w \ne s

。

:

\mathrm{dist}(s, s) = 0

으로 둔다.

:

\mathrm{dist}(s, w) = \min \{ \mathrm{dist}(s, v) + c(v, w) \mid (v, w) \in E \}

가 성립한다.

단일 시작점의 경우, 간선의 가중치(

c(s, v)

)가 1이면 너비 우선 탐색을, 0 이상이면 다익스트라 알고리즘을, 그 외의 경우에는 벨만-포드 알고리즘을 사용할 수 있다. 변의 가중치가 음이 아닌 두 정점 간의 최단 경로 문제에서 최단 경로의 거리 하한값을 알고 있다면, A* 알고리즘을 사용하면 다익스트라 알고리즘보다 빠르게 구할 수 있다.

다음은 단일 출발점 최단 경로 알고리즘과 관련된 표이다.

알고리즘	계산량	제작자
벨만-포드 알고리즘	$O(VE)$
다익스트라 알고리즘 (리스트)	$O(V^2)$
다익스트라 알고리즘 (수정된 이진 힙)	$O((E+V) \log{V})$
다익스트라 알고리즘 (피보나치 힙)	$O(E+V \log{V})$

3. 1. 1. 무방향 그래프

다익스트라 알고리즘은 음이 아닌 가중치를 갖는 그래프에서 최단 경로를 찾는 데 사용된다.^[5] 이 외에도 다양한 알고리즘이 존재하며, 그래프의 특성에 따라 적합한 알고리즘을 선택해야 한다. 다음은 무방향 그래프에서 최단 경로를 찾는 몇 가지 알고리즘이다.

너비 우선 탐색: 가중치가 없는 그래프에서 최단 경로를 찾는다. 시간 복잡도는 ''O''(''E'' + ''V'')이다.

다음 표는 일부 수정 및 추가 사항이 있다. 녹색 배경은 표에서 점근적으로 최상의 경계를 나타낸다. ''L''은 정수 간선 가중치를 가정할 때 모든 간선 중 최대 길이(또는 가중치)이다.

가중치	알고리즘	시간 복잡도	저자
$\mathbb{R}$		$O(V^2EL)$	Ford, 1956
$\mathbb{R}$	벨만-포드 알고리즘	$O(VE)$	Shimbel, 1955; Bellman, 1958; Moore, 1959
$\mathbb{R}$		$O(V^2 \log{V})$	Dantzig, 1960
$\mathbb{R}$	다익스트라 알고리즘 (리스트 사용)	$O(V^2)$	Leyzorek 외, 1957; Dijkstra, 1959; Minty (Pollack & Wiebenson, 1960 참조); Whiting & Hillier, 1960
$\mathbb{R}$	다익스트라 알고리즘 (이진 힙 사용)	$O((E+V)\log{V})$	Johnson, 1977
$\mathbb{R}$	다익스트라 알고리즘 (피보나치 힙 사용)	$O(E+V\log{V})$	Fredman & Tarjan, 1984; Fredman & Tarjan, 1987
$\mathbb{R}$	양자 다익스트라 알고리즘 (인접 리스트 사용)	$O(\sqrt{VE}\log^2{V})$	Dürr 외, 2006^[4]
$\mathbb{N}$	다이얼 알고리즘^[5] (다익스트라 알고리즘 사용, L개의 버킷을 가진 버킷 큐)	$O(E+LV)$	Dial, 1969
		$O(E\log{\log{L}})$	Johnson, 1981; Karlsson & Poblete, 1983
	개보 알고리즘	$O(E\log_{E/V}L)$	Gabow, 1983; Gabow, 1985
		$O( E + V \sqrt{\log{L}})$	Ahuja, Mehlhorn, Orlin & Tarjan, 1990
$\mathbb{N}$	토럽	$O(E+V \log{\log{V}})$	Thorup, 2004

3. 1. 2. 방향 비순환 그래프(DAG)

위상 정렬을 사용하는 알고리즘은 임의의 가중치를 갖는 방향 비순환 그래프(DAG)에서 단일 출발점 최단 경로 문제를 시간에 해결할 수 있다.^[3]

3. 1. 3. 방향 그래프

다익스트라 알고리즘은 음이 아닌 가중치만을 갖는 단일 출발점 최단 경로 문제를 해결한다.
벨만-포드 알고리즘은 간선 가중치가 음수일 수 있는 경우 단일 출발점 문제를 해결한다.
A* 검색 알고리즘은 검색 속도를 높이기 위해 휴리스틱을 사용하여 단일 쌍 최단 경로를 해결한다.
플로이드-워셜 알고리즘은 모든 쌍 최단 경로 문제를 해결한다.
존슨 알고리즘은 모든 쌍 최단 경로 문제를 해결하며, 희소 그래프에서 플로이드-워셜 알고리즘보다 빠를 수 있다.
비터비 알고리즘은 각 노드에 추가적인 확률 가중치를 사용하여 최단 확률 경로 문제를 해결한다.

알고리즘	시간 복잡도	저자
너비 우선 탐색	O(E + V)

음수 사이클을 찾거나 모든 정점까지의 거리를 계산한다.

가중치	알고리즘	시간 복잡도	저자
$\mathbb{Z}$		$O(E\sqrt{V}\log{N})$	앤드루 V. 골드버그

3. 2. 모든 쌍 최단 경로 알고리즘

플로이드-워셜 알고리즘은 모든 쌍 최단 경로 문제를 해결한다. 존슨 알고리즘도 모든 쌍 최단 경로 문제를 해결하며, 희소 그래프에서 플로이드-워셜 알고리즘보다 빠를 수 있다.^[1]

4. 점화식

$V$ 를 정점, $E$ 를 간선, $c(s, v)$ 를 간선의 가중치, $\mathrm{dist}(s, v)$ 를 최단 경로의 거리라고 할 때, $s, v, w \in V$ 이고 $w \ne s$ 이면 다음이 성립한다.

: $\mathrm{dist}(s, s) = 0$

: $\mathrm{dist}(s, w) = \min \{ \mathrm{dist}(s, v) + c(v, w) \mid (v, w) \in E \}$

단일 시작점의 경우 $c(s, v) = 1$ 이면 너비 우선 탐색을, $c(s, v) \ge 0$ 이면 다익스트라 알고리즘을, 그렇지 않으면 벨만-포드 알고리즘을 사용할 수 있다.^[2]

5. 응용

최단 경로 알고리즘은 다양한 현실 문제 해결에 활용된다.

웹 지도 등에서 실제 위치들 사이의 경로를 자동으로 탐색하여 운전 방향을 잡아주고, 명확한 경로를 찾는 데 응용된다.
비결정적 추상 기계로 표현되는 문제에서 목표 상태에 도달하기 위한 최적의 선택 순서를 찾거나, 주어진 상태에 도달하는 시간의 하한선을 구하는 데 사용될 수 있다. 예를 들어, 루빅스 큐브의 해답을 찾는 데 응용할 수 있다.
네트워크 또는 통신망에서는 최소-지연 경로 문제라고도 하며, 최광폭 경로 문제와 함께 다루어진다.
6단계 분리 게임에서 같은 영화에 출연하는 영화배우들을 나타내는 그래프의 최단 경로를 찾는 데 응용되기도 한다.
네트워크 흐름은 그래프 이론 및 운영 과학의 기본 개념으로, 상품, 액체, 정보 등이 네트워크를 통해 운송되는 문제를 모델링하는 데 사용된다.

5. 1. 교통 및 운송

웹 지도 웹사이트(예: 구글 지도)와 같이 물리적 위치 간의 길찾기를 자동으로 찾는 데 최단 경로 알고리즘이 적용된다.^[10] 또한, 역스파토, 에키탄, NAVITIME 등과 같은 철도 경로 안내 서비스에서도 최단 경로 문제가 활용된다. 이 서비스들은 역을 노드로, 역과 역 사이의 소요 시간을 가중치로 하는 에지로 철도 선로를 그래프화하여 최단 경로를 구한다.

5. 2. 네트워크

컴퓨터 네트워크 또는 통신망 관점에서 최단 경로 문제는 최소-지연 경로 문제라고도 하며, 일반적으로 최대 대역폭 경로 문제와 관련이 있다. 예를 들어, 최단 (최소-지연) 최대 대역폭 경로 또는 최대 대역폭 최단 (최소-지연) 경로를 찾을 수 있다.^[11]

5. 3. 로봇 공학 및 게임

대니 첸은 운영 연구, 공장 설비 배치, 로봇공학, 수송, VLSI 설계 등에 최단 경로 문제가 응용될 수 있음을 언급하였다.^[6]

'''로봇 경로 계획''': 로봇이 주어진 환경에서 목표 지점까지 최단 경로로 이동하도록 경로를 계획하는 데 사용된다.
'''게임 AI''': 게임 캐릭터가 목표 지점까지 최단 경로로 이동하거나, 플레이어에게 최적의 경로를 제시하는 데 사용된다.

5. 4. 기타

대니 첸은 최단 경로 문제가 운영 과학, 공장 설비 배치, 로봇공학, 수송, VLSI 설계 등에 응용될 수 있음을 언급하였다.^[6]

운영 과학: 공장 설비 배치, 자원 할당 등 다양한 운영 과학 문제 해결에 활용된다.
VLSI 설계: 초고밀도 집적 회로(VLSI) 설계 시 배선 경로 최적화에 사용된다.
6단계 분리 (Six Degrees of Separation): 6단계 분리 게임은 같은 영화에 출연하는 영화배우들을 나타내는 그래프에서 최단 경로를 찾는 데에 응용된다. 즉, 사회 연결망에서 임의의 두 사람이 몇 단계를 거쳐 연결될 수 있는지 분석하는 데 활용된다.

6. 관련 문제

외판원 문제(Traveling Salesman Problem, TSP): 모든 노드를 한 번씩 방문하고 시작 노드로 돌아오는 최단 경로를 찾는 문제이다. NP-완전 문제로, 효율적인 해법이 알려져 있지 않다.^[17]
중국 우체부 문제(Chinese Postman Problem): 모든 간선을 한 번 이상 지나고 시작점으로 돌아오는 최단 경로를 찾는 문제이다.
최장 경로 문제(Longest Path Problem): 그래프에서 가장 긴 경로를 찾는 문제이다. NP-완전 문제이다.^[2]
유클리드 최단 경로: 계산 기하학에서의 최단 경로 문제이다.
제약 조건 최단 경로 문제: 원하는 해 경로에 추가적인 제약 조건을 포함하는 최단 경로 문제로, 해결하기가 더 어렵다.^[16]

7. 추가 정보

캐나다 여행자 문제와 확률적 최단 경로 문제는 그래프가 이동자에게 완전히 알려져 있지 않거나, 시간에 따라 변하거나, 행동(통과)이 확률적인 경우를 일반화한 것이다.^[18]^[19]

7. 1. 확률적 시간 종속 네트워크에서의 최단 경로

실생활에서 교통 네트워크는 일반적으로 확률적이며 시간에 따라 변동한다.^[26]^[27] 도로 구간의 이동 시간은 교통량(기점-종점 매트릭스), 도로 공사, 날씨, 사고, 차량 고장 등 여러 요인에 따라 달라지기 때문이다. 이러한 도로 네트워크의 현실적인 모델은 확률적 시간 종속(STD) 네트워크이다.^[26]^[27]

불확실한, 즉 확률적 도로 네트워크에서 최적 경로에 대한 합의된 정의는 아직 없다. 이는 지난 10년간 상당한 진전에도 불구하고 논쟁의 여지가 있는 주제이다. 일반적인 정의는 최소 기대 이동 시간을 갖는 경로이다. 이 접근 방식은 결정론적 네트워크에 효율적인 최단 경로 알고리즘을 사용할 수 있다는 장점이 있다. 그러나 이동 시간의 변동성을 고려하지 않기 때문에, 결과로 나오는 최적의 경로는 신뢰할 수 없을 수 있다.

이 문제를 해결하기 위해 일부 연구자들은 기대값 대신 이동 시간 분포를 사용한다. 이들은 동적 프로그래밍 및 다익스트라 알고리즘과 같은 최적화 방법을 사용하여 총 이동 시간의 확률 분포를 찾는다.^[28] 이러한 방법은 확률적 최적화, 특히 확률적 동적 프로그래밍을 사용하여 확률적 아크 길이를 갖는 네트워크에서 최단 경로를 찾는다.^[29] "이동 시간 신뢰성" 및 "이동 시간 변동성"은 교통 연구 문헌에서 반대되는 개념으로 사용된다. 즉, 변동성이 높을수록 예측의 신뢰성은 낮아진다.

변동성을 고려하기 위해 연구자들은 불확실성 하에서 최적 경로에 대한 두 가지 대안적 정의를 제시했다. "가장 신뢰할 수 있는 경로"는 이동 시간 예산 내에 정시에 도착할 확률을 최대화하는 경로이다. "α-신뢰성 경로"는 주어진 확률로 정시에 도착하는 데 필요한 이동 시간 예산을 최소화하는 경로이다.

7. 2. 음수 사이클 감지

경우에 따라 주요 목표는 최단 경로를 찾는 것이 아니라 그래프에 음수 사이클이 있는지 감지하는 것이다. 일부 최단 경로 알고리즘은 이러한 목적으로 사용할 수 있다.

벨만-포드 알고리즘은 $O(|V||E|)$ 시간에 음수 사이클을 감지할 수 있다.
체르카스키와 골드버그는 음수 사이클 감지를 위한 여러 다른 알고리즘을 조사했다.^[20]

참조

_[1] 서적 The Shortest-Path Problem https://link.springe[...]
_[2] 서적 Graph Theory with Applications to Engineering and Computer Science https://books.google[...] Courier Dover Publications 2016-08-17
_[3] harvnb 2001
_[4] 간행물 Quantum query complexity of some graph problems 2006-01
_[5] 간행물 Algorithm 360: Shortest-Path Forest with Topological Ordering [H]
_[6] 서적 Introduction to Algorithms MIT Press 2009-07-31
_[7] 서적 Algorithm Design http://www.nytimes.c[...] Addison-Wesley
_[8] arXiv A Quantum Algorithm for Finding the Minimum 1996-07-18
_[9] arXiv Quantum algorithms for shortest paths problems in structured instances 2014-10-22
_[10] 웹사이트 Fast route planning https://www.youtube.[...] 2009-03-23
_[11] 웹사이트 K-Shortest Paths Q-Routing: A New QoS Routing Algorithm in Telecommunication Networks https://doi.org/10.1[...] Springer, Berlin, Heidelberg 2005
_[12] 간행물 Developing algorithms and software for geometric path planning problems 1996-12
_[13] 문서 Highway Dimension, Shortest Paths, and Provably Efficient Algorithms http://research.micr[...] ACM-SIAM Symposium on Discrete Algorithms 2010
_[14] 문서 A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks http://research.micr[...] Symposium on Experimental Algorithms 2011
_[15] 간행물 Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems
_[16] 간행물 On an exact method for the constrained shortest path problem 2013
_[17] 서적 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019
_[18] 간행물 The canadian traveller problem 1991
_[19] 컨퍼런스 Route planning under uncertainty: the Canadian traveller problem https://www.aaai.org[...]
_[20] 간행물 Negative-cycle detection algorithms https://doi.org/10.1[...] 1999-06-01
_[21] 컨퍼런스 Sur des algorithmes pour des problèmes de cheminement dans les graphes finis Dunod (Paris); Gordon and Breach (New York) 1967
_[22] 서적 Problèmes de cheminement dans les graphes Dunod (Paris)
_[23] 서적 Path Problems in Networks https://books.google[...] Morgan & Claypool Publishers 2010-04-04
_[24] 서적 Graphs, Dioids and Semirings: New Models and Algorithms Springer Science & Business Media
_[25] 서적 Generic Inference: A Unifying Theory for Automated Reasoning John Wiley & Sons
_[26] 문서 Optimal paths in graphs with stochastic or multidimensional weights. 1983
_[27] 간행물 Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm 2015
_[28] 간행물 Finding shortest path in a combined exponential – gamma probability distribution arc length 2014
_[29] 간행물 Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length 2014

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com